import java.util.Arrays;

public class MergeSortNonRecursion {
    public static void mergeSort(int[] array){
        //归并排序非递归实现
        int groupNum = 1;// 每组的数据个数
        while(groupNum < array.length){
            // 无论数组含有几个元素， 数组每次都需要从下标 0位置，开始遍历。
            for(int i = 0;i<array.length;i+= groupNum * 2){
                int low = i;
                int mid = low + groupNum -1;

                // 防止越界
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int high = mid + groupNum;

                // 防止越界
                if(high >= array.length){
                    high = array.length-1;
                }
                merge(array,low,mid,high);
            }
            groupNum *= 2;
        }
    }
    public static void merge(int[] array,int low,int mid,int high){
        if(high == mid){
            return;
        }
        int[] arr = new int[high -low + 1];
        int start1 = low;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = high;
        int i = 0;
        while(start1 <= end1 && start2 <= end2){
            if(array[start1]>array[start2]){
                arr[i++] = array[start2++];
            }else{
                arr[i++] = array[start1++];
            }
        }
        while (start1 <= end1){
            arr[i++] = array[start1++];
        }
        while(start2 <= end2){
            arr[i++] = array[start2++];
        }
        for (int j = 0; j < arr.length; j++) {
            array[low++] = arr[j];
        }
    }

    public static void main(String[] args) {
        int[] array = {12,5,8,7,3,4,1,10};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
